package j2025.j01;

import java.util.ArrayList;
import java.util.List;

public class j0105 {
    /**
     * 78. 子集
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
     * 子集
     * （幂集）。
     *
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     */
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int index){
        ret.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size()-1);
        }
    }


    /**
     * 17. 电话号码的字母组合
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     *
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     */
    String[] phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    StringBuilder Path;
    List<String> Ret;

    public List<String> letterCombinations(String digits) {
        Path = new StringBuilder();
        Ret = new ArrayList<>();
        if(digits.length() == 0){
            return Ret;
        }
        DFS(digits,0);
        return Ret;
    }
    public void DFS(String digits,int index){
        if(index == digits.length()){
            Ret.add(Path.toString());
            return;
        }
        String tmp = phone[digits.charAt(index)-'0'];
        for (int i = 0; i < tmp.length(); i++) {
            Path.append(tmp.charAt(i));
            DFS(digits,index+1);
            Path.deleteCharAt(Path.length()-1);
        }
    }

    /**
     * 39. 组合总和
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
     * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
     * 并以列表形式返回。你可以按 任意顺序 返回这些组合。
     *
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     *
     * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
     */
    List<List<Integer>> rrr;
    List<Integer> tmp;
    int cou,t;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        t = target;
        cou = 0;
        rrr = new ArrayList<>();
        tmp = new ArrayList<>();
        Dfs(candidates,0);
        return rrr;
    }
    public void Dfs(int[] candidates,int index){
        if(cou==t){
            rrr.add(new ArrayList<>(tmp));
            return;
        }else if(cou>t){
            return;
        }
        for (int i = 0; i < candidates.length; i++) {
            if(i<index){
                continue;
            }
            cou += candidates[i];
            tmp.add(candidates[i]);
            Dfs(candidates,i+1);
            tmp.remove(tmp.size()-1);
            cou -= candidates[i];
        }
    }
}
